package com.xj.algorithm.leetcode;

import java.util.HashMap;
import java.util.Map;

/**
 * 最长回文串
 */
public class L409_组合字符串中的字符组成最长回文串 {

    /**
     * 给定一个包含大写字母和小写字母的字符串，找到通过这些字母构造成的最长的回文串。
     *
     * 在构造过程中，请注意区分大小写。比如 "Aa" 不能当做一个回文字符串。
     *
     * 注意:
     * 假设字符串的长度不会超过 1010。
     *
     * 示例 1:
     *
     * 输入:
     * "abccccdd"
     *
     * 输出:
     * 7
     *
     * 解释:
     * 我们可以构造的最长的回文串是"dccaccd", 它的长度是 7。
     */
    public static void main(String[] args) {
        System.out.println(longestPalindromeOffice("abccccdd"));
    }

    //自己的解法：使用hashMap找对子
    public static int longestPalindrome(String s) {
        int len=s.length();
        int sum=0;
        Map<Character,Integer> map=new HashMap<>();
        for(int i=0;i<len;i++){
            Integer count=map.get(s.charAt(i));
            if(count==null){
                map.put(s.charAt(i),1);
            }else{
                sum+=2;
                map.remove(s.charAt(i));
            }
        }
        if(map.size()!=0){
            sum++;
        }
        return sum;
    }

    //官方解法：贪心算法，成双成对再+1
    public static int longestPalindromeOffice(String s) {
        int[] count = new int[128];
        for (char c: s.toCharArray())
            count[c]++;

        int ans = 0;
        for (int v: count) {
            ans += v / 2 * 2;   //处理奇数和偶数
            if (v % 2 == 1 && ans % 2 == 0)     //处理对称中心
                ans++;
        }
        return ans;
    }
}
